
/**
 * @file 	flow_network.h
 * @author  Alessandro Carrega <contact@alexcarrega.com>
 * @version 2.0
 *
 * \class FlowNetwork
 *
 * \ingroup GraphMaxFlow
 *
 * \brief Rete di Flusso con possibilità di calcolare il massimo flusso di grafo.
 * 
 * @secion LICENSE
 *
 * This file is part of graph_max_flow.
 *
 * graph_max_flow is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * graph_max_flow is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with graph_max_flow.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * @section DESCRIPTION
 *
 * Modella il Grafo con possibiltà di aggiungere nuovi nodi e ne calcolare 
 * il flusso massimo a partire da un nodo source fino a un  node sink.
 *
 */

#ifndef FLOW_NETWORK_H
#define FLOW_NETWORK_H

#include "queue.h"

class FlowNetwork {

public:
	/**
	 * \brief Crea una nuova rete di flusso.
	 * \param[in] num_node numero di nodi del grafo
	 * \param[in] num_edge numero di edge del grafo
	 */ 
	FlowNetwork(int num_node, int num_edge);
	/**
	 * \brief Aggiunge un nuovo edge tra \p u e \p v con capacità \p cap.
	 * \param[in] u nodo sorgente dell'edge
	 * \param[in] v nodo finale dell'edge
	 * \param[in] cap capacità dell'edge
	 */
	void add_edge(int u, int v, int cap);
	/**
	 * \brief Calcola il flusso massimo tra i nodi \p source e \p sink.
	 * \param[in] source nodo sorgente 
	 * \param[in] sink nodo finale
	 * \return Il massimo flusso del grafo tra i nodi \p source e \p sink
	 *
	 * \sa Queue
	 * 
	 */
	int max_flow(int source, int sink);

private:
	/**
	  * \brief Indica se è presente un path tra i nodi \p source e \p sink.
	  * \param[in] source nodo sorgente 
	  * \param[in] sink nodo finale
	  * \return Ritorna TRUE se esiste il path, altrimenti FALSE
	  * 
	  * Se il percorso esiste viene memorizzato in FlowNetwork::precedent_
	  * che sarà usato dal metodo FlowNetwork::max_flow.
	  * L'algoritmo usato è \b BFS.
	  * 
	  * \sa Queue
	  */
	bool has_path(int source, int sink);

private:
	/**
	 * \brief Capacità degli edge, gli indici indicano i nodi.
	 * \par Esempio:
	 * \code capacity_[u][v] \endcode contiene la capacità dell'edge
	 * che collega i nodi \p u e \p v.
	 */
	int **capacity_; 
	/**
	 * \brief Flusso degli edge, gli indici indicano i nodi.
	 * \par Esempio:
	 * \code flow_[u][v] \endcode contiene il flusso dell'edge
	 * che collega i nodi \p u e \p v.
	 */
	int **flow_;
	/**
	 * \brief Contiene il nodo precedente nel percorso (se esiste) calcolato nella funzione FlowNetwork::has_path.
	 * \par Esempio:
	 * \code precedent_[v] == u \endcode se vero vuol dire che l'edge
	 * tra il nodo \p u e \p v fa parte del percorso tra \p source e \p sink.
	 */
	int *precedent_;
	Queue q_; ///< coda usata in FlowNetwork::has_path
	int num_node_, ///< numero di nodi del grafo
		num_edge_; ///< numero di edge del grafo
};

#endif // FLOW_NETWORK_H
